Chapter 3: Databases

What is a database(3)
Exercise 3-3(2)

Count the number of non-ID columns in the following database and compare to the number of foreign keys in the database schema.

Employee FName WorksIn Mngr
1 Alan 101 2
2 Ruth 101 2
3 Kris 102 3
Dept DName Secr
101 Sales 1
102 IT 3

Solution(1)

They are the same: 5

Categories(30)
Free Categories(7)
Category(1)

A category, \(\mathcal{C}\)

  • Need to specify a collection of objects, \(Ob(\mathcal{C})\)

  • For every two objects c and d, one specifies a set \(\mathcal{C}(c,d)\) called morphisms from c to d

    • This set is called the hom-set and morphism is a shorthand for homomorphism

  • For every object c one specifies a morphism \(id_c \in \mathcal{C}(c,c)\) called the identity morphism

  • For every pair of morphisms \(c \xrightarrow{f} d\) and \(d \xrightarrow{g} e\), one specifies a morphism \(c \xrightarrow{f;g}e\) called the composite of f and g

  • Furthermore, these must satisfy two conditions:

    1. unitality: composing with identities does not change anything

    2. associativity: \((f;g);h = f;(g;h)\)

Linked by

Free category on a graph(1)

The category \(\mathbf{Free}(G)\), given a graph \(G=(V,A,s,t)\)

  • A category whose objects are vertices and morphisms are paths.

  • The identity morphism is the trivial path at any vertex.

  • Composition is path concatenation (this obeys unitality and associativity)

Linked by

Naturals as category(1)

  • The natural numbers as a free category: \(\boxed{\overset{\bullet}{z}\circlearrowleft s}\)

  • There are infinitely many paths, in bijection with the natural numbers.

  • This is a category with one object, also called a monoid.

  • The composition operation corresponds to the addition operation.

  • Unitality and associativity give us the usual constraints on a monoid.

Linked by

Exercise 3-10(2)

The free category \(3 := \mathbf{Free}(\boxed{\overset{v_1}\bullet \xrightarrow{f_1}\overset{v_2}{\bullet}\xrightarrow{f_2}\overset{v_3}{\bullet}})\) has three objects and six morphisms. Give the morphisms names and write out the composition operation in a 6x6 matrix. Which are the identities?

Solution(1)

Identities are 1,2,3

\(\circ\) 1 2 3 f1 f2 f12
1 1 f1 f12
2 2 f2
3 3
f1 f1 f12
f2 f2
f12 f12
Exercise 3-12(2)

  1. What is the category 1?

  2. What is the category 0?

  3. What is the formula for the number of morphisms in n?

Solution(1)

  1. It has one object and one (identity) morphism.

  2. It has zero objects and zero morphisms.

  3. \(1+2+...+n\), i.e. \(\frac{n(n+1)}{2}\)

Categories via path equations(5)

We can add constraints to a free category which states that two paths are equal

Exercise 3-17(2)

Write down all the morphisms in the free category presented by the following diagram:

Solution(1)

A,B,C,D,f,h,g,i,j

Exercise 3-19(2)

What are the morphisms in the following category: \(\boxed{\overset{\bullet}{z}\circlearrowleft s\ \ \boxed{s;s;s;s = s;s}}\)

Solution(1)

z,s,ss,sss

Preorders and free categories - two ends of a spectrum(5)

  • Takeaway: A preorder is a category where every two parallel arrows are the same.

  • Any preorder can be considered a category, and any category can be crushed down into a preorder (called preorder reflection).

    • The objects are the elements of the set, and there is a single morphism between a and b iff \(a \leq b\)

  • Considering a preorder as a category is right adjoint to turning a category into a preorder by preorder reflection.

  • Every category presentation lies somewhere between the free category and the preorder reflection.

Exercise 3-21(2)

What equations are needed to add to the following graphs in order to present the associated preorders?

Solution(1)

  1. f=g

  2. f;f=f

  3. f;h=g;i

  4. none are needed

Exercise 3-22(2)

What is the preorder reflection of the category \(\mathbb{N}\) from Example 3.13

Solution(1)

The trivial preorder of one object.

Important categories in mathematics(3)

  • What are commonly called categories are actually Set-categories, in the terminology of \(\mathcal{V}\) categories.

  • There are many important categories:

    • Top - topological spaces (neighborhood)

    • Grph - graphs (connection)

    • Meas - measure spaces (amount)

    • Mon - monoids (action)

    • Grp - groups (reversible action, symmetry)

    • Cat - categories (action in context, structure)

The category Set(1)

The category of sets, denoted Set

  • Objects are the collection of all sets.

  • Morphisms are set-functions

  • Composition is function composition (satsifies associativity), identities are the identity functions (satisfies identity constraints).

  • Closely related is the subcategory FinSet of finite sets with morphisms being set-functions.

Opposite category(1)

Any category \(\mathcal{C}\) induces another category, \(\mathcal{C}^{op}\) defined as the same objects but all arrows reversed.

Isomorphisms in a category(10)

Isomorphisms formalize the notion of ‘interchangibility’, e.g. in a preorder the fact that \(a \cong b\) tells us that it doesn’t matter whether someone tells us \(c \leq a\) versus \(c \leq b\).

Isomorphism(1)

An isomorphism in a category

  • A morphism \(A \xrightarrow{f}B\) such that there exists a morphism \(B \xrightarrow{g}A\) satisfying \(f;g=id_A\) and \(g;f=id_B\)

  • We call f and g inverses and can write \(g=f^{-1}\)

  • We say A,B are isomorphic objects in this case.

Linked by

Set isomorphism(1)

The set \(\{a,b,c\}\) and \(\bar{3}\) are isomorphic (we have \(3!\) bijections to choose from). The isomorphisms in Set are the bijections.

Retraction(1)

  • It is possible for \(f;g=id\) but \(g;f \ne id\)

  • This is called a retraction rather than an isomorphism.

Exercise 3-31(2)

Show that the identity arrow on any given object is an isomorphism.

Solution(1)

The inverse to \(id_c\) exists; it is itself: \(id_c ; id_c = id_c\) (from the identity property)

Exercise 3-32(2)

A monoid in which every morphism is an isomorphism is known as a group

  1. Is the natural numbers monoid a group?

  2. Is the monoid with the added constraint \(s;s=z\) a group?

Solution(1)

  1. No, \(s\) has no inverse (no natural number can be added to 1 to get 0)

  2. Yes, this is the cyclic group with two elements.

Exercise 3-33(2)

Someone says that the only isomorphisms in \(\mathbf{Free}(G)\) for some graph \(G\) are the identity morphisms. Are they correct?

Solution(1)

They are correct. If we could compose \(f;g\) to get a morphisms from c to c, a free category would pick a new morphism rather than re-use the identity (which could be forced with a constraint).

Functors, natural transformations, and databases(33)
Sets and functions as databases(1)

  • We can think of sets as 1-table databases and functions as 2-table databases.

  • Any database takes a presentation of category, turns each vertex into a set and each arrow into a function.

Functors(11)
Functor(1)
Example between small categories(1)

  • Between the free square category and the commutative square category, there is no functor from the commutative square category to the free square category which keeps the corners in the same place.

  • If we did this, we’d have \(F(f;h)=F(g;i)\) (since these are the same morphism).

  • The functor rules would allow us to break this up into \(F(f);F(h)=F(g);F(i)\) and we don’t have a choice for those mappings other than \(f;h=g;i\), something that is not true in the free square category.

Functor between preorders(1)

Functors between preorders are monotone maps. Morphisms in the source must map to sources in the target, so if \(a \leq_P b\), then we require \(F(a) \leq_Q F(b)\), which is tantamount to the monotone map constraint.

Exercise 3-37(2)

How many functors are there from 2 to 3?

Solution(1)

We are only concerned about where the objects go, since the target category is a thin category (there is no choice about which morphism is mapped to). Thus the functors are: 11, 22, 33, 12, 23, 13

Exercise 3-39(2)

Say where each of the 10 morphisms in the free square category are mapped to by a functor to the commutative square category (where \(Ob(F)\) maps each corner to the same corner).

Solution(1)

The four identity morphisms and four length-1 paths are trivially mapped to the the corresponding morphisms. Both length-2 paths in the free category are mapped to the same morphism, \(f;h\).

Exercise 3-40(2)

Consider \(\mathcal{C}=\boxed{\bullet \rightarrow \bullet}\) and \(\mathcal{D}=\boxed{\bullet \rightrightarrows \bullet}\). Give two functors that act the same on objects but differently on morphisms.

Solution(1)

Let the two functors map the left object to the left object and right object to the right object. The first functor maps the nontrivial morphism to the upper morphism in \(\mathcal{D}\), whereas the second maps it to the lower morphism.

Exercise 3-43(2)

  1. Given a category \(\mathcal{C}\), show that there exists a functor \(id_\mathcal{C}\) known as the identity functor on \(\mathcal{C}\)

  2. Show that given \(\mathcal{C}\xrightarrow{F}\mathcal{D}\) and \(\mathcal{D}\xrightarrow{G}\mathcal{E}\) we can define a new functor \(\mathcal{C}\xrightarrow{F;G}\mathcal{E}\) just by composing functions.

  3. Show that there is a category, let’s call it Cat where the objects are categories, morphisms are functors, and identities/composition are given as above.

Solution(1)

  1. Mapping objects and morphisms to themselves satsifies the functor constraints of preserving identities and composition.

  2. If \(F,G\) both independently preserve identity arrows, then composition of these will also preserve this. Also \(G(F(f;g))=G(F(f);F(g))=G(F(f));G(F(g))\) using the independent facts that \(F,G\) each preserve composition.

  3. Composition of identity functions do not change anything, so the identity functor (defined by identity function) will obey unitality. Because function composition is associative and functor composition is defined by this, we also satisfy that constraint.

Database instances as Set-valued functors(5)

Just like all sets are instances on the schema 1, all functions are instances on the schema 2.

Database instance(1)

A \(\mathcal{C}\) instance, where \(\mathcal{C}\) is a schema, i.e. a finitely-presented category.

A functor \(\mathcal{C} \xrightarrow{I} \mathbf{Set}\)

Linked by

Database instance example(1)

  • Consider the following category: \(\boxed{\overset{\bullet}{z}\circlearrowleft s\ \ \boxed{s;s = s}}\)

  • A functor from this category to Set is a set \(Z\) and a involution function \(Z \rightarrow Z\).

    • \(Z =\) natural numbers and a function sending everything to zero (zero is sent to zero)

    • \(Z =\) set of well-formed arithmetic expressions (e.g. \(12+(2*4)\)) and a function which evaluates to an integer (which itself is a well-formed expression). Evaluation on integers does nothing.

    • A function which sends numbers greater than 2 to their smallest prime factor (this is a no-op on the prime factors themselves).

Exercise 3-45(2)

For any functor \(\mathbf{1} \xrightarrow{F} \mathbf{Set}\) one can extract a set, \(F(1)\). Show that for any set \(S\) there is a functor \(\mathbf{1}\xrightarrow{F_S}\mathbf{Set}\) such that \(F_S(1)=S\)

Solution(1)

Define \(F_S\) to send the object of 1 to \(S\) and preserve identity morphisms. There is no nontrivial composition to enforce, so this is a valid functor.

Natural transformations(11)
Natural transformation(1)

A natural transformation \(F \overset{a}\Rightarrow G\) between two functors (going from \(\mathcal{C}\) to \(\mathcal{D}\)).

  • For each object \(c \in \mathcal{C}\), one specifies a morphism \(F(c)\xrightarrow{\alpha_c}G(c)\) in \(\mathcal{D}\) called the c-component of \(\alpha\)

  • These components must satisfy the naturality condition: for each morphism \(c \xrightarrow{f} d\) in \(\mathcal{C}\) we need \(F(f);\alpha_d=\alpha_c;G(f)\)

  • AKA this diagram should commute:

Linked by

Diagram(1)

A diagram \(\mathcal{D}\) in a category \(\mathcal{C}\)

  • A functor \(\mathcal{J}\xrightarrow{D}\mathcal{C}\) from any category \(\mathcal{J}\) called the indexing category of the diagram \(D\).

  • We say \(D\) commutes if \(D(f)=D(f')\) for every parallel pair of morphisms \(f,f'\) in \(\mathcal{J}\)

Functor category(1)

The functor category from categories \(\mathcal{C}\) to \(\mathcal{D}\)

\(\mathcal{D}^\mathcal{C}\) has all functors \(\mathcal{C} \rightarrow \mathcal{D}\) as objects and natural transformations as morphisms.

Linked by

Small natural transformation example(1)

  • The natural transformation requires us to choose morphisms in the righthand category for each object in the lefthand category

  • The only choices to satisfy the naturality condition are \(c\) and \(g\).

Natural transformation to unit(1)

  • Just like sets are in bijection with functors \(\mathbf{1}\rightarrow\mathbf{Set}\), we can also associate natural transformations

    with functions.

  • In the language of functor categories, this claim is to say \(\mathbf{Set}^1\) is equivalent to \(Set\).

Linked by

Natural transformations between sequences(1)

  • Any non-decreasing sequence of naturals can be identified with a functor \(\mathbb{N}\rightarrow \mathbb{N}\), considering the preorder of naturals as a category.

  • A natural transformation between two of these functors would require a component \(\alpha_n\) for each natural, which means a morphism from \(F_n \rightarrow G_n\). This exists iff \(F(n)\leq G(n)\).

  • Thus we can put a preorder structure over the monotone map of \(\mathbb{N} \rightarrow \mathbb{N}\) (this is a thin functor category \(\mathbb{N}^\mathbb{N}\)).

Natural isomorphism of Bool-categories and preorders(1)

  • There exists a category PrO which has preorders as objects and monotone maps as morphisms.

  • There exists a category *Bool-Cat* in which the objects are Bool-categories and morphisms are Bool-functors.

  • We call these categories equivalent because there exist functors \(\mathbf{PrO}\overset{F}{\underset{G}{\rightleftarrows}}\mathbf{BoolCat}\) such that there exist natural isomorphisms \(F;G \cong id_\mathbf{PrO}\) and \(G;F \cong id_\mathbf{Bool-Cat}\)

Exercise 3-55(2)

Let’s investigate why the functor category is actually a category.

  1. Figure out how to compose natural transformations \(F \xrightarrow{\alpha} G \xrightarrow{\beta}H\).

  2. Propose an identity natural transformation on any functor and check that it is unital.

Solution(1)

  1. The individual natural transformations satsifying the naturality condition makes the left and right squares commute, meaning the whole diagram commutes:

    • Thus the mapping from objects in \(F\)’s domain to morphisms in \(H\)’s codomain is given by \(G;\beta\).

  2. Mapping each object to its own identity morphism will satisfy the naturality condition (all four edges of the square become identity functions). This will enforce unitality.

Exercise 3-58(2)

Let \(\mathcal{C}\) be an arbitrary category and \(\mathcal{P}\) be a preorder thought of as a category. Are the following true?

  1. For any two functors \(\mathcal{C}\xrightarrow{F,G}\mathcal{P}\), there is at most one natural transformation \(F \rightarrow G\)

  2. For any two functors \(\mathcal{P}\xrightarrow{F,G}\mathcal{C}\), there is at most one natural transformation \(F \rightarrow G\)

Solution(1)

  1. This is true: there are no choices to be made for a natural transformation, given that for each morphism \(c\rightarrow d\) in \(\mathcal{C}\) we have to pick \(\alpha_c\) to be the morphism \(F(c)\rightarrow G(c)\) and \(\alpha_{d}\) to be the morphism \(F(d)\rightarrow G(d)\).

  2. Counterexample:

    • let \(F\) send \(f\mapsto x,a\mapsto1,b\mapsto 2\) and \(G\) maps everything to \(2\)

    • The naturality condition for f leaves us with two choices for \(\alpha_a\)

The category of instances on a schema(5)
Instance homomorphism(1)

An instance homomorphism between two database instances, \(\mathcal{C}\xrightarrow{I,J}\mathbf{Set}\)

Grph as functor category(1)

  • The category of graphs as a functor category

  • Schema for graphs: \(\mathbf{Gr}:=\boxed{\overset{Arr}\bullet \overset{src}{\underset{tar}{\rightrightarrows}}\overset{Vert}\bullet}\)

  • A graph instance has a set of points and a set of arrows, each of which has a source and target.

  • There is a bijection between graphs and Gr instances

  • The objects of GrInst are graphs, the morphisms are graph homomorphisms (natural transformations between two Gr to Set functors)

    • Each graph homomorphism contains two components, which are morphisms in Set:

      1. \(G(Vert) \xrightarrow{\alpha_{vert}} H(vert)\)

      2. \(G(Arr) \xrightarrow{\alpha_{arr}} H(Arr)\)

    • Naturality conditions

Arrow table(1)

  • Consider the graphs \(G:=\boxed{\overset{1}\bullet \xrightarrow{a} \overset{2}\bullet \xrightarrow{b}\overset{3}\bullet}\) and \(H:=\boxed{\overset{4}\bullet \overset{d}{\underset{c}{\rightrightarrows}}\overset{5}\bullet\circlearrowleft e}\)

  • The arrow table of their database instances are below:

  • G src tar
    a 1 2
    b 2 3

  • H src tar
    c 4 5
    d 4 5
    e 5 5

Linked by

Exercise 3-64(2)

Consider the graphs \(G,H\) from Example 3.63. We claim there is exactly one graph homomorphism such that \(\alpha_{Arr}(a)=d\). What is the other value of \(\alpha_{Arr}\), and what are the three values of \(\alpha_{Vert}\)?

Solution(1)

  • We need \(2 \mapsto 5\), so the source of \(\alpha_{Arr}(b)\) must be \(5\) (there is only one arrow to pick, \(e\)).

  • \(1 \mapsto 4,\ 2\mapsto 5,\ 3 \mapsto 5\)

Adjunctions and data migration(17)
Pulling back data along a functor(4)
Functor pullback(1)

The pullback of functor \(\mathcal{D}\xrightarrow{I}\mathbf{Set}\) along functor \(\mathcal{C}\xrightarrow{F}\mathcal{D}\)

  • The composite functor \(\mathcal{C}\xrightarrow{F;I}\mathbf{Set}\)

  • Given a natural transformation \(I \overset{\alpha}\Rightarrow J\), there is a natural transformation \(\alpha_F\) whose components (morphisms in Set from \((F;I)(c)\) to \((F;J)(c)\), for any \(c \in \mathcal{C}\) are given by: \((\alpha_F)_c := \alpha_{F(c)}\)

DDS pullback(1)

  • Pulling back data along a functor

  • We’ll migrate data between the graph-indexing schema Gr and the loop schema, called DDS (for discrete-dynamical system).

  • We’ll write down an example instance \(\mathbf{DDS}\xrightarrow{I}\mathbf{Set}\)

State Next
1 4
2 4
3 5
4 5
5 5
6 7
7 6

  • We want to convert this state information into a graph that will let us visualize our machine.

  • Use the following functor \(F\):

    • src is sent to identity

    • Can now generate a graph using the composite functor \(\mathbf{Gr}\xrightarrow{F}\mathbf{DDS}\xrightarrow{I}\mathbf{Set}\)

Arr src tar
1 1 4
2 2 4
3 3 5
4 4 5
5 5 5
6 6 7
7 7 6

\(Vert = \bar{7}\)

  • We can now draw the graph:

  • This procecure can be called “pulling back data along a functor". We pulled back data \(I\) along functor \(F\) (via functor composition).

Linked by

Exercise 3-67(2)

Consider the functor \(\mathbf{Gr}\xrightarrow{G}\mathbf{DDS}\) given by sending src to next and tar to id on State. Migrate the same data as in Example 3.65 and draw the corresponding graph.NOCARD

Solution(1)
Arr src tar
1 4 1
2 4 2
3 5 3
4 5 4
5 5 5
6 7 6
7 6 7

Adjunctions(6)
Adjoint functor(1)

A functor \(\mathcal{C}\xrightarrow{L}\mathcal{D}\) is left adjoint to a functor \(\mathcal{D}\xrightarrow{R}\mathcal{C}\)

  • For any \(c \in C\) and \(d \in D\), there is an isomorphism of hom-sets: \(\alpha_{c,d}: \mathcal{C}(c,R(d)) \xrightarrow{\cong} \mathcal{D}(L(c),d)\) that is natural in c and d.

  • Given a morphism \(c \rightarrow{f} R(d)\) in \(\mathcal{C}\), its image \(g:=\alpha_{c,d}(f)\) is called its mate (and vice-versa)

  • To denote the adjunction we write \(L \dashv R\) or

Linked by

Galois connections are adjoint(1)

Galois connections between preorders are the same as adjunctions between the corresponding categories.

Currying(1)

The adjunction called currying says \(\mathbf{Set}(A \times B,C)\cong \mathbf{Set}(A,C^B)\)

Linked by

Adjoint examples(1)

Examples of adjunctions

  1. Free constructions: given a set you get a free groupmonoidring/vector space/etc. - each of these is a left adjoint. The corresponding right adjoint throws away the algebraic structure.

  2. Given a graph you get a free preorder or a free category, the corresponding right adjoint is the underlying graph of a preorder/category.

  3. Discrete things: given any set you get a discrete preordergraphmetric spacecategorytopological space/etc.; each of these is a left adjoint and the corresponding right adjoint again recovers the set.

  4. Codiscrete things: given any set you get a codiscrete preorder, complete graph, codiscrete category, category, etc.; each of these is a right adjoint and the left adjoint gives the underlying set.

  5. Given a group, you can quotient by its commutator subgroup to get an abelian group; this is a left adjoint. The right adjoint is the inclusion of abelian groups into Grp

Exercise 3-73(2)

Currying was an adjunction between functors in Set, but the example only discussed what the functors did to objects.

  1. Given a morphism \(X \xrightarrow{f}Y\), what morphism should \(X \times B \xrightarrow{-\times B}Y\times B\) return?

  2. Given a morphism \(X \xrightarrow{f}Y\), what morphism should \(X^ B \xrightarrow{(-)^B}Y^B\) return?

  3. Consider \(\mathbb{N}\times \mathbb{N}\xrightarrow{+}\mathbb{N}\). Currying \(+\), we get a certain function \(\mathbb{N}\xrightarrow{p}\mathbb{N}^\mathbb{N}\). What is \(p(3)\)?

Solution(1)

  1. This morphism maps \((x,b)\mapsto (f(x),b)\)

  2. This morphism takes in a function \(B \xrightarrow{bx} X\) and composes with f to give \(B \xrightarrow{bx;f} Y\)

  3. It takes a number and returns a function which adds three to that number.

Left and right pushforward functors(2)

Given \(\mathcal{C}\xrightarrow{F}\mathcal{D}\), the data migration functor \(\Delta_F\) turns \(\mathcal{D}\) instances to \(\mathcal{C}\) instances. This functor has both a left and right adjoint:

Migration Functor Pronounced Reminiscent of Database idea
\(\Delta\) Delta Duplicate or destroy Duplicate or destroy tables or columns
\(\Sigma\) Sigma Sum Union (sum up) data
\(\Pi\) Pi Product Pair and query data
Plane tickets(1)

  • Consider a functor which discards the distinction between Economy and First Class seats in an airplane.

  • The \(\Delta\) functor is uninteresting - it will copy the rows for Seat into both Economy and First class.

  • The functor \(\Pi\) puts into each airline seat only seats which are in both the Economy and First Class tables with the same price and position.

  • The functor \(\Sigma\) puts all Economy and First Class seats into the Seat table and discards the information of from which table they came from.

Single set summaries of databases(5)
Emails(1)

  • Consider the schema \(\mathfrak{g} := \boxed{\overset{Email}\bullet \overset{sentBy}{\underset{receivedBy}{\rightrightarrows}} \overset{Address}\bullet}\)

  • And an example instance: \(\mathfrak{g}\xrightarrow{I}\mathbf{Set}\)

Email SentBy ReceivedBy
1 Bob Grace
2 Grace Pat
3 Bob Emmy
4 Sue Doug
5 Doug Sue
6 Bob Bob

  • Data migration functors \(\Sigma_!,\Pi_!\) go from \(\mathcal{C}\) Inst to 1-Inst, but we showed that 1-Inst is equivalent to Set in Example 3.53.

  • \(\Sigma_!\) tells us the mailing groups, the "connected components" in \(I\):

1
Bob-Grace-Pat-Emmy
Sue-Doug

  • \(\Pi_!\) tells us the emails that were sent from a person to themselves

    1
    \(Em_6\) (Bob)

Linked by

Exercise 3-76(2)

For any category \(\mathcal{C}\) there is exactly one functor to the category 1, let’s call it \(!\) Where does it send each object and each morphism?

Solution(1)

There is only one object to send each object to and only one morphism to send each morphism to. Because everything in the target is equal to everything else, all functor constraints are trivially satisfied.

Exercise 3-78(2)

Draw the instance \(I\) in Example 3.77 as a graph.NOCARD

Solution(1)

Introduction to limits and colimits(37)
Terminal objects and products(17)
Terminal object(1)

terminal object in a category \(\mathcal{C}\)

  • An object z is terminal if, for each object c there exists a unique morphism \(c \xrightarrow{!} z\)

  • We say terminal objects have a universal property

Linked by

Product(1)

Given two objects \(X,Y \in \mathcal{C}\), the product \(X \times Y\)

  • This is another object in \(\mathcal{C}\) with morphisms \(X \xleftarrow{p_x}X\times Y\xrightarrow{p_y}Y\)

  • This should satisfy the property that there exists a unique morphism making the following diagram commute for any other object C and morphisms \(X \xleftarrow{f}C\xrightarrow{g}Y\)

Linked by

Terminal in Set(1)

In Set, any set with exactly one element is a terminal object. For an arbitrary other set, we have no choice but to send everything to that one object when specifying a function.

Product in Set(1)

  • In Set, the categorical product of two sets is our usual cartesian product.

  • The projections are \(x \xrightarrow{p_x}(x,y)\xrightarrow{p_y}y\)

  • The unique morphism from some \(X \xleftarrow{f} C \xrightarrow{g} Y\), the unique map \(C \xrightarrow{!}X \times Y\) is given by \((f\times g)(c):=(f(c),g(c))\).

Product in Cat(1)

The product of two categories \(\mathcal{C}\times \mathcal{D}\) may be given as follows:

  • \(Ob(C\times D)\) are the pairs \((c,d)\) where c is an object of \(\mathcal{C}\) and d is an object of \(\mathcal{D}\).

  • Morphisms are pairs \((c,d)\xrightarrow{(f,g)}(c',d')\) where \(c \xrightarrow{f}c'\) is a morphism in \(\mathcal{C}\) and \(d \xrightarrow{g}d'\) is a morphism in \(\mathcal{D}\).

  • Composition is given by composing each entry in the pair separately.

Linked by

Terminal objects are isomorphic(2)
Proof(1)

  • Suppose \(Z,Z'\) are both terminal objects. Therefore there exist unique maps \(Z \overset{a}{\underset{b}{\rightleftarrows}}Z'\)

  • Composing these we get \(Z \xrightarrow{a;b} Z\), but this is forced to be the identity map because there is only one morphism from \(Z\) to itself and we have to have an identity.

  • Therefore we can talk about ’the terminal object’ as if there were only one.

All terminal objects in a category \(\mathcal{C}\) are isomorphic

Exercise 3-81(2)

Let \(z \in P\) be an element of a preorder, and consider the corresponding category \(\mathcal{P}\). Show that z is a terminal object iff it is a top element in \(P\), i.e. \(\forall c \in P: c \leq z\)

Solution(1)

There is a morphism from every object if every object is less than z, and the uniqueness comes from the fact that preorders are thin categories.

Exercise 3-82(2)

Name a terminal object in the category Cat

Solution(1)

1 is terminal because a functor from any other category is forced to map all objects to 1 and all morphisms to its identity morphism.

Exercise 3-83(2)

Name a category which does not have a terminal object

Solution(1)

The category corresponding to the natural numbers has no terminal object (it would be an integer larger than all integers).

Exercise 3-88(2)

Let \(x,y \in P\) be elements of a preorder and \(\mathcal{P}\) be the corresponding category. Show that the product \(x \times y\) in \(\mathcal{P}\) agrees with their meet \(x \land y\) in \(P\).

Solution(1)

  • The uniqueness aspect of the product is not relevant since all morphisms are unique in a preorder category.

  • The product definition translates to an operation which takes a pair of objects in a preorder and gives us another object with the property that \(x \times y \leq x\) and \(x \times y \leq y\), and for any other b that also has this property we have \(b \leq x\times y\)

  • Considering the set \(A=\{x,y\}\), the conditions for \(x \times y\) matches the definition of \(\bigwedge A\) (grestest lower bound).

Exercise 3-90(2)

  1. What are identity morphism in a product category \(\mathcal{C}\times \mathcal{D}\)?

  2. Why is composition in a product category associative?

  3. What is the product category \(1 \times 2\)?

  4. What is the product category of two preorders?

Solution(1)

  1. For object \((c,d)\), the identity morphism is \((id_c,id_d)\)

  2. The operation was defined in terms of function composition which is associative.

  3. It is isomorphic to just 2

  4. The underlying set is the cartesian product, and \((a,b)\leq(a',b')\) iff \(a \leq a' \land b \leq b'\)

Limits(8)

  • How is the product (and its unique map) related to terminal objects?

  • Call \(\mathbf{Cone}(X,Y)\) the /category of cones over X and Y in/ \(\mathcal{C}\), given two objects in \(\mathcal{C}\).

    • An object is pair of maps \(X \xleftarrow{f}C\xrightarrow{g}Y\) for some \(c \in \mathcal{C}\)

    • A morphism a from \(X \xleftarrow{f}C\xrightarrow{g}Y\) to \(X \xleftarrow{f'}C\xrightarrow{g'}Y\) is a morphism \(C \rightarrow C'\) in \(\mathcal{C}\) such that the following diagram commutes:

Free diagram(1)

  • Suppose \(\mathcal{J}\) is the free category on the graph \(\boxed{1 \rightarrow 2 \leftarrow 3 \rightrightarrows 4 \rightarrow 5}\)

  • We may draw a diagram \(\mathcal{J}\xrightarrow{D}\mathcal{C}\) inside \(\mathcal{C}\) as below:

  • \(\boxed{D_1 \rightarrow D_2 \leftarrow D_3 \rightrightarrows D_4 \rightarrow D_5}\)

  • We can represent this diagram as a cone over the diagram by picking a \(C \in \mathcal{C}\) for which every pair of parallel paths that start from \(C\) are the same.

Terminal object as limit(1)

Terminal objects are imits where the indexing category is empty, \(\mathcal{J}=0\).

Product as limit(1)

Products are limits where the indexing category consists of two objects with no arrows, \(\mathcal{J}=\boxed{\overset{v}\bullet\ \overset{w}\bullet}\).

Linked by

Cone(1)

A cone \((C,c_*)\) over a diagram \(\mathcal{J}\xrightarrow{D}\mathcal{C}\) and the category \(\mathbf{Cone}(D)\)

  • We require:

    • An object \(C \in Ob(\mathcal{C})\)

    • For each object \(j \in \mathcal{J}\), a morphism \(C \xrightarrow{c_j}D(j)\).

  • The following property must be satisfied:

    • \(\forall f \in \mathcal{J}(j,k):\) \(c_k=c_j;D(f)\)

  • A morphism of cones is a morphism \(C \xrightarrow{a} C'\) in \(\mathcal{C}\) such that, for all \(j \in \mathcal{J}\), we have \(c_j=a;c'_j\).

  • Cones and their morphisms form a category.

Linked by

Limit(1)

The limit of a diagram \(D\), \(lim(D)\)

  • The limit of \(D\), denoted is the terminal object in the category \(\mathbf{Cone}(D)\)

  • If \(lim(D)=(C,c_*)\) we refer to \(C\) as the limit object and the map \(c_j\) as the jth projection map

Linked by

Exercise 3-91(2)

Check that the product \(X \xleftarrow{p_X} X \times Y \xrightarrow{p_Y} Y\) is terminal object in \(\mathbf{Cone}(X,Y)\)

Solution(1)

The existence and uniqueness of the morphism to the product object in the product definition are the conditions of being a terminal object in \(\mathbf{Cone}(X,Y)\). The maps of the terminal object to \(X\) and \(Y\) are the projection maps of the product.

Finite limits in Set(9)

  • This section shows that a database instance \(\mathcal{J}\xrightarrow{I}\mathbf{Set}\) is a diagram in Set. Also the functor \(\Pi_!\) takes the limit of this diagram.

  • Details not presented, but it suffices to work with just the finitely-presented graph of \(\mathcal{J}\) rather than the category itself (path equations not relevant for this).

Limit formula(2)

  • Let \(\mathcal{J}\) be a category presented by the finite graph \((\{v_1,...,v_n\},A,s,t)\) with some equations.

  • Let \(\mathcal{J}\xrightarrow{D}\mathbf{Set}\) be some set-valued functor.

  • The set \(\underset{\mathcal{J}}{lim}D := \{(d_1,...,d_n)\ |\ \forall i: d_i \in D(v_i)\ \text{and}\ \forall v_i\xrightarrow{a}v_j \in A: D(a)(d_i)=d_j\}\)

    • ... together with projection maps \(lim_\mathcal{J}D \xrightarrow{p_i}D(v_i)\) given by \(p_i(d_1,...,d_n):=d_i\)

  • ... is a limit of \(D\). NOCARD

Proof(1)

NOT PROVEN

Linked by

Terminal object in limit formula(1)

  • With respect to Proposition 3.95, if \(\mathcal{J}=0\), then \(n=0\); there are no vertices.

  • There is exactly one empty tuple which vacuously satisfies the properties, so we’ve constructed the limit as the singleton set \(\{()\}\) consisting of just the empty tuple.

  • Thus the limit of the empty diagram, i.e. the terminal object in Set, is the singleton set.

Pullback diagram(1)

  • If \(\mathcal{J}\) is presented by the cospan graph \(\boxed{\overset{x}\bullet \xrightarrow{f} \overset{a}\bullet \xleftarrow{g}\overset{y}\bullet}\) then its limit is known as a pullback.

  • Given the diagram \(X \xrightarrow{f}A\xleftarrow{g}Y\), the pullback is the cone shown below:

  • Because the diagram commutes, the diagonal arrow is superfluous. One can denote pullbacks instead like so:

  • The pullback picks out the \((X,Y)\) pairs which map to the same output.

Exercise 3-97(2)

  • Show that the limit formula works for products in Set

  • The diagram, whose limit is a product, is \(\mathcal{J}=\boxed{\overset{v}\bullet\ \overset{w}\bullet}\) (see Exaample 3.94)

Solution(1)

  • \(V=\{v,w\}, A=\varnothing\)

  • The second condition of the set comprehension is vacuously satisfied because \(A = \varnothing\)

  • So all we have left is all pairs of tuples where the first element comes from \(D(v)\) and the second element comes from the set \(D(w)\).

  • This is the Cartesian product \(D(v) \times D(w)\)

Exercise 3-99(2)

If \(1 \xrightarrow{D}\mathbf{Set}\) is a functor, what is the limit of \(D\)? Compute using the limit formula and check answer against the limit definition.

Solution(1)

  • There are no arrows, so we just recover the set \(D(1)\) as the limit.

  • The limit definition first requires the category \(\mathbf{Cone}(1)\)

    • There is only one possible cone, so \(Cone(1)\cong 1\)

  • The terminal object in \(1\) is the sole object of the category.

A brief note on colimits(3)
Cocone(1)

A cocone in a category \(\mathcal{C}\)

  • A cone in \(\mathcal{C}^{op}\)

  • Given a diagram \(\mathcal{J}\xrightarrow{D}\mathcal{C}\), we may take the limit of the functor \(\mathcal{J}^{op}\xrightarrow{D^{op}}\mathcal{C}^{op}\) is a cocone in \(\mathcal{C}\) - the colimit of \(D\) is this cocone.

Exercise 3-101(2)

Let \(\mathcal{C}\xrightarrow{F}\mathcal{D}\) be a functor. How should we define its opposite: \(\mathcal{C}^{op}\xrightarrow{F^{op}}\mathcal{D}^{op}\)

Solution(1)

  • There is an isomorphism between a category and its opposite, meaning there are natural functors \(\overset{\cong}\rightarrow\) which alternate between them.

  • Define \(\mathcal{C}^{op}\xrightarrow{F^{op}}\mathcal{D}^{op}\) as \(F ; \overset{\cong}\rightarrow\). This is a valid functor as it is the composition of two functors.